Building on the trace from the previous slide, we now analyze Selection Sort's performance characteristics, which are defined by its quadratic time complexity and efficient use of memory.
- Selection Sort's time complexity is dominated by comparisons. The outer loop runs $n-1$ times, and the inner loop performs a linear scan, resulting in a total comparison count that is always $O(n^2)$.
- This performance is consistent for the Best, Average, and Worst cases, making Selection Sort a non-adaptive algorithm—its runtime does not improve on already-sorted data.
- Key Property: Instability. Selection Sort is inherently unstable. A swap can move an element from the start of the unsorted section to the end, disrupting the relative order of equal-valued elements.
- The algorithm is in-place, requiring only a constant amount of extra memory ($O(1)$) for variables, making it highly space-efficient.
| Case | Time Complexity | Auxiliary Space | Stability | In-Place |
|---|---|---|---|---|
| Worst Case | $O(n^2)$ | $O(1)$ | Unstable | Yes |
| Average Case | $O(n^2)$ | $O(1)$ | Unstable | Yes |
| Best Case (Already Sorted) | $O(n^2)$ | $O(1)$ | Unstable | Yes |